The present invention relates to the technical domain of cryptography, and more precisely of the so-called asymmetric or public key cryptography.
In this type of cryptography, each user holds a pair of keys, consisting of a secret key and of an associated public key, for a given use.
For example, if one is dealing with a key pair dedicated to confidentiality, then the public key is used to encrypt the data, while the secret key is used to decrypt them, i.e. to decipher these data. If one is dealing with a key pair dedicated to data authenticity, then the secret key is used to digitally sign the data, while the public key is used to verify the digital signature. Other uses (entity authentication, exchange of keys, etc.) are possible.
Public key cryptography is very useful insofar as, unlike secret key cryptography, it does not require the parties involved to share a secret in order to set up a secure communication. However, this advantage in terms of security is accompanied by a disadvantage in terms of performance, since the public key cryptography methods (also called “public key schemes”) are, for equal resources, often a hundred or a thousand times slower than the so-called secret key cryptography methods (also called “secret key schemes”). As a result, to obtain reasonable calculation times, the cost of the circuits implementing these algorithms is often very high.
This is particularly true of the so-called RSA digital encryption and signature scheme (see R. L. Rivest, A. Shamir and L. M. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM, Vol. 21, No. 2, pp. 120-126, February 1978). This scheme relies on the difficulty of the problem of integer factorization: given a large integer (typically more than 1,000 bits in its representation in base 2) equal to the product of two or more prime factors of comparable sizes, no efficient procedure exists for retrieving these prime factors. The calculations performed in this scheme therefore relate to very large numbers. They cannot be performed in less than a second on a chip card unless the latter is fitted with a specialized cryptographic coprocessor, which considerably increases its cost. Moreover, since the efficiency of factorization procedures is growing fairly rapidly with time, key lengths often have to be revised upward, to the detriment of performance.
The question of reducing the cost of chips implementing public key schemes therefore arises.
There are principally two approaches for tackling this question. The first consists in specifying new cryptographic schemes, preferably (but not necessarily) based on problems other than factorization, which make it possible to significantly speed up the calculation times. This avenue is much explored, and has given rise to numerous results. However, in the great majority of cases, either the improvement compared with RSA is not significant enough to envisage the replacement thereof, or security has not been sufficiently well established.
The second approach consists in manufacturing chips in such quantity that their cost decreases in large proportion. This is what will perhaps happen with RSA if the international banking organizations confirm the choice of this scheme for future chip-based bank cards. However, the cost of an RSA chip is so high at the outset that it will always remain substantial, whatever the number of chips fabricated.
It will be noted that many public key cryptographic schemes have in common the use of operations on integers as basic operations, such as modular multiplications (ab (modulo n)), modular divisions (a/b (modulo n)), or modular exponentiations (ab (modulo n)), where a, b and n are integers. However, these operations are never exactly the same. Consequently, each time the cryptographic scheme is modified, it is necessary to change the program or the circuit of the security device which performs the cryptographic calculations.
An object of the present invention is to decrease the cost of public key cryptographic units by combining the two approaches above.